// https://leetcode.cn/problems/find-mode-in-binary-search-tree/
// Created by ade on 2022/8/8.
//
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    // 最简单的方法，中序+map,但是空间复杂度O(n);
    int maxCount = 1;
    int base = INT_MIN; // 当前节点的数值
    int count = 0; // 当前节点对应的数量
    vector<int> res = {};

    vector<int> findMode(TreeNode *root) {
        dfs(root);
        return res;
    }

    // 空间复杂度O(1)
    void dfs(TreeNode *root) {
        if (!root) return;
        dfs(root->left);
        if (base != root->val) {
            base = root->val;
            count = 1;
//            if (maxCount == 0) maxCount = 1;
        } else {
            count++;
        }
        if (count > maxCount) {
            maxCount = count;
            res.clear();
            res.push_back(root->val);
        } else if (count == maxCount) {
            res.push_back(root->val);
        }
        dfs(root->right);
    }
};
